#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param n: Given the range of numbers
    @param k: Given the numbers of combinations
    @return: All the combinations of k numbers out of 1..n
    """
    def combine(self, n, k):
        # 对于顺序不做要求
        self.ret = []

        if 0 in [n, k]:
            return self.ret

        self.n = n
        self.k = k

        self.rec_combine(1, [])
        return self.ret

    # def loop_combine(self):
    #     # 循环版本
    #     pass

    def rec_combine(self, begin, path):
        # 类似 q17-subsets.py, 但是加入了self.k检测(结束检测: push result).
        # remain检测: 及时剪枝
        path_len = len(path)
        if path_len == self.k:
            self.ret.append(path)
            return

        remain = self.k - path_len      # 还需要追加多少个元素

        for i in range(begin, self.n+1):
            # print(begin, i, path)
            if self.n - i + 1 < remain:
                return
                # break

            self.rec_combine(i+1, path + [i])


def main():
    print("start main")
    s = Solution()
    ret = s.combine(20, 10)
    print(ret)

if __name__ == "__main__":
    main()
